#include<iostream>
#include<climits>
using namespace std;
const int MAXSIZE=10;
template <class T>
class MGraph
{
private:
    T vertex[MAXSIZE];
    int arc[MAXSIZE][MAXSIZE];
    int vNum,arcNum;
public:
    MGraph(ifstream &fin);
    ~MGraph();
    void DFS(int v);
    void BFS(int v);
    void ShortPath(int v,int Disk[],int Path[]);
    int FindMin(int Disk[],bool S[],int n);
    void Print(int Disk[],int Path[],int n);
};
template <class T>
MGraph<T>::MGraph(ifstream &fin)
{
    fin>>vNum;
    fin>>arcNum;
    for (int i = 0; i < vNum; i++)
    {
        fin>>vertex[i];
    }
    for (int i = 0; i < vNum; i++)
    {
        for (int j = 0; j < vNum; j++)
        {
            fin>>arc[i][j];
        }
    }
}
template <class T>
MGraph<T>::~MGraph()
{

}
template <class T>
void MGraph<T>::ShortPath(int v,int Disk[],int Path[])
{
    bool S[MAXSIZE];
    for (int i = 0; i < vNum; i++)
    {
        S[i]=false;
        Disk[i]=arc[v][i];
        if (Disk[i]!=INT_MAX)
        {
            Path[i]=v;
        }
        else
        {
            Path[i]=-1;
        }
    }
    S[v]=true;
    Disk[v]=0;
    for (int  i = 0; i < vNum; i++)
    {
        if ((v=FindMin(Disk,S,vNum))==-1)
        {
            return;
        }
        S[v]=true;
        for (int j = 0; j < vNum; j++)
        {
            if (! S[j]&&(Disk[j]>arc[v][j]+Disk[v]))
            {
                Disk[j]=arc[v][j]+Disk[v];
                Path[j]=v;
            }
        }
    }
    Print(Disk,Path,vNum);
}
template <class T>
int MGraph<T>::FindMin(int Disk[],bool S[],int n)
{
    int k=0,min=INT_MAX;
    for (int  i = 0; i < n; i++)
    {
        if (! S[i]&&min>Disk[i])
        {
            min=Disk[i];
            k=i;
        }
        if(min==INT_MAX)
        {
            return -1;
        }
        return k;
    }
}
template <class T>
void MGraph<T>::Print(int Disk[],int Path[],int n)
{
    for (int i = 0; i < n; i++)
    {
        cout<<'V'<<i<<':'<<Disk[i]<<"\t{V"<<i;
        int pre=Path[i];
        while (pre!=-1)
        {
            cout<<'V'<<pre;
            pre=Path[pre];
        }
        cout<<"}"<<endl;
    }
}